今天是紀錄LeetCode解題的第四天
來看一題困難題

第四題題目：Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
給定兩個排序數組num1和num2，大小分別是m、n，傳回兩個排序數組的中位數
時間複雜度是O(log (m+n))

中位數定義：一個有序數組裡中位數把數組分成兩個部分，當數組長度為偶數時，中位數為左邊數組的最大值加右邊數組最小值的平均，當數組長度為奇數時，中位數只有一個，也就是整個數組最中間的元素值

這題如果不限制時間複雜度，最簡單的方法就是合併兩個陣列再排序，接著找最中心的元素就好，但這樣總體時間複雜度為O((n+m)log(n+m))，所以我們要用二分搜尋的方式來解這題

我們原本的作法是合併數組並找出中間的元素，而二分搜尋的方法則是把A、B兩個數組，分別取i、j分割點，將A、B各分為左邊數組和右邊數組，並且確保1.左邊數組元素數量和右邊數組元素數量相等或左邊數組元素數量比右邊數組元素數量多1個，2.左邊數組所有元素值<=右邊數組所有元素值

我們來看統整概念

變數意義

程式碼如下

m,n = len(nums1),len(nums2)
        if m > n: #確保在短的串列上做二分，避免超出串列範圍
            nums1, nums2, m, n = nums2, nums1, n, m
        left,right = 0,m
        while left <= right:
            i = (left + right) // 2
            j = (m + n + 1) // 2 - i

            maxLeftA = float('-inf') if i == 0 else nums1[i-1]
            minRightA = float('inf') if i == m else nums1[i]
            
            maxLeftB = float('-inf') if j == 0 else nums2[j-1]
            minRightB = float('inf') if j == n else nums2[j]

            if maxLeftA <= minRightB and maxLeftB <= minRightA:
                if (m+n) % 2 == 0:
                    return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2
                else:
                    return max(maxLeftA, maxLeftB)
            elif maxLeftA > minRightB:
                right = i - 1
            else: #maxLeftB > minRightA
                left = i + 1

執行過程

總結

1. 不合併數組 → 利用已排序特性
2. 在長度較短的數組二分搜尋切割點i
3. 對應計算長度較長數組切割點j
4. 判斷切割點是否在數組範圍內，小於數組範圍 → 負無限大、大於數組範圍 → 無限大
5. 比較左右最大/最小值判斷是否切割正確
6. 切割正確後算中位數
   奇數 → max(maxLeftA, maxLeftB)
   偶數 → (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2